\chapter[On the Expressiveness of Synchronous/Polyadic Communication]{On the Expressiveness of Synchronous and Polyadic Communication}
\label{chap:separa}
\minitoc

In this chapter we study the expressiveness of synchronous and polyadic communication
in higher-order process calculi. 
We thus consider extensions of \hocore with restriction and polyadic communication.
We present both encodabilty and impossibility results:
first we show that 
asynchronous
process-passing is expressive enough so as to encode
synchronous communication. Then, we show that a similar result for
polyadic communication does not hold. In fact, 
we show that 
a hierarchy of synchronous higher-order process calculi based on the arity of
polyadic communications is induced.
Finally, we examine the influence abstraction passing has in the expressiveness of the considered calculi.
Central to our results is the fact that 
the establishment of \emph{private links} ---as available in first-order concurrency---
is not possible in the absence of name-passing.

Section \ref{s:calculus} introduces the families of higher-order process calculi 
we shall be working with. 
Section \ref{s:enc-result} presents and discusses the encodability result of synchronous into asynchronous communication.
Section \ref{s:sepresults} presents separation results
for encodings involving polyadic communication, whereas Section \ref{s:abstraction}
discusses the power of abstraction passing.
%In Section \ref{s:discuss} we comment further on our notion of encoding.
Section \ref{s:conc} concludes.

The separation results for the expressiveness of polyadic communication have been
published as an extended abstract in \citep{LanesePSS09}; all the other results
and discussions are original to this dissertation.

\input{impos-aux}